Using Euclids Extended Algorithm:
Calculate x and y in Bézout's Identity
using (13,385)
For 2 numbers a and b and divisor d:
ax + by = d
a math | a | b math | b | d math | d | k math | k |
---|---|---|---|---|---|---|---|
Set to 1 | 1 | Set to 0 | 0 | 13 | |||
Set to 0 | 0 | Set to 1 | 1 | 385 | Quotient of 13/385 | 0 | |
1 - (0 x 0) | 1 | 0 - (0 x 1) | 0 | Remainder of 13/385 | 13 | Quotient of 385/13 | 29 |
0 - (29 x 1) | -29 | 1 - (29 x 0) | 1 | Remainder of 385/13 | 8 | Quotient of 13/8 | 1 |
1 - (1 x -29) | 30 | 0 - (1 x 1) | -1 | Remainder of 13/8 | 5 | Quotient of 8/5 | 1 |
-29 - (1 x 30) | -59 | 1 - (1 x -1) | 2 | Remainder of 8/5 | 3 | Quotient of 5/3 | 1 |
30 - (1 x -59) | 89 | -1 - (1 x 2) | -3 | Remainder of 5/3 | 2 | Quotient of 3/2 | 1 |
-59 - (1 x 89) | -148 | 2 - (1 x -3) | 5 | Remainder of 3/2 | 1 | Quotient of 2/1 | 2 |
89 - (2 x -148) | 385 | -3 - (2 x 5) | -13 | Remainder of 2/1 | 0 | Quotient of 1/0 | 0 |
a = -148 and b = 5
ax + by = gcd(a,b)
13x + 385y = gcd(13